package com.dyz.swordFingerOffer;

/**
 * @author: daiyizheng
 * @date: 2021/6/1 21:22
 * @description:
 */
public class HasSubtree26 {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1==null || root2==null){
            return false;
        }
        return dfs(root1, root2);
    }
    //找根节点
    public boolean dfs(TreeNode node, TreeNode root2){
        boolean flag = false;
        if (node.val==root2.val){
            //相等
            flag =  judge(node,root2);
        }
        //
        if(flag){
            return true;//通过当前节点已经找到二叉树B的完全匹配结果， 就没有必要再往下去遍历二叉树A了。
        }
        boolean flag1 = false;//用来记录当前节点的左子树中的查找结果（其实也是包含了比较过程）
        boolean flag2 = false;//用来记录当前节点的右子树中的查询结果（其实也是包含了比较过程）
        //左右节点的深度遍历
        if(node.left!=null){ flag1 = dfs(node.left, root2);} //当前节点的val不等于二叉树B的root值，那么就去遍历当前节点的左子树，看否找得到二叉树B
        if(node.right!=null){flag2 =dfs(node.right, root2);}//当前节点的val不等于二叉树B的root值，那么就去遍历当前节点的右子树，看否找得到二叉树B

        return flag1||flag2;

    }
    //找到根节点后开始深度遍历
    public boolean judge(TreeNode root1, TreeNode root2){
        //中止条件
        if(root2==null){
            return true; //说明二叉树B的某个方向的节点已经完全的匹配成功了
        }
        if(root1==null){
            return false;//说明在某个方向上，二叉树A中的节点不缺少的，二叉树B还有子节点。
        }
        if (root1.val==root2.val){
            //定义左右节点返回值
            boolean flag1 = true;
            boolean flag2 = true;
            if(root1.left!=null || root2.left!=null){ // 这里要注意 是|| 不是&&
                flag1 = judge(root1.left, root2.left);
            }
            if(root1.right!=null || root2.right!=null){
                flag2 = judge(root1.right, root2.right);
            }
            return flag1 && flag2; //深度遍历阶段左右节点要全部相等
        }else{
            return false;
        }
    }
}
